package JZ.JZ16;

/**
 * @author corn
 * @create 2020-07-22-10:37
 */

/**
 * 合并两个排序的链表
 * 题目描述
 * 输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。
 */
public class MergeLists {

}
class Solution {
    public ListNode Merge(ListNode list1,ListNode list2) {
        //方式二：递归
        if (list1 == null) {
            return list2;
        } else if (list2 == null) {
            return list1;
        }else{
            if(list1.val<list2.val){//通过此，将两个链表的头结点中数值小的结点作为放回的头结点。
                list1.next=Merge(list1.next, list2);
                return list1;
            }else {
                list2.next=Merge(list1, list2.next);
                return list2;
            }
        }
    }
}

//class Solution {
//    public ListNode Merge(ListNode list1,ListNode list2) {
//        //方式一：遍历两个链表，按大小顺序拼接
//        //头结点
//        ListNode head = new ListNode(-1);
//        //从头结点开始，逐步向后添加结点
//        ListNode moveNode = head;
//        while(list1 !=null &&list2 !=null){
//            if(list1.val <= list2.val){
//                moveNode.next = list1;
//                list1 = list1.next;
//            }else{
//                moveNode.next = list2;
//                list2 = list2.next;
//            }
//            moveNode = moveNode.next;
//        }
//        moveNode.next = (list1!=null) ? list1 : list2;
//        return head.next;
//    }
//}

class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}
